package org.chronologger.poppaea.client.overlap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

import com.google.gwt.user.client.Window;

public class OverlapResolver implements Iterable<OverlapGroup> {

	private class RangeInfo {
		public int top;
		public int height;
		public OverlapGroup group;
	}

	private int height;

	private List<OverlapGroup> overlapGroups = new ArrayList<OverlapGroup>();
	private HashMap<Range, RangeInfo> rangeMapping = new HashMap<Range, RangeInfo>();

	public void setHeight(int height) {
		this.height = height;
	}

	public int getHeight() {
		return this.height;
	}

	/**
	 * Returns the overlap group corresponding to a range.
	 * 
	 * @param range
	 * @return
	 */
	public OverlapGroup getGroup(Range range) {
		return rangeMapping.get(range).group;
	}

	/**
	 * Adds a range to this overlap resolver and recomputes positions.
	 * 
	 * @param range
	 */
	public void addRange(Range range) {
		// try to find an overlap group
		OverlapGroup targetGroup = null;

		for (OverlapGroup group : overlapGroups) {
			if (Range.Tools.overlapping(group, range)) {
				targetGroup = group;
				break;
			}
		}

		if (targetGroup == null) {
			// none found, create a new one
			targetGroup = new OverlapGroup();
			overlapGroups.add(targetGroup);
		}

		targetGroup.addRange(range);
		RangeInfo info = new RangeInfo();
		info.group = targetGroup;
		rangeMapping.put(range, info);

		joinGroups();
		updateGroupPositions();

		Window.setTitle(overlapGroups.size() + " groups");
	}

	/**
	 * Call this when a range has changed.
	 * 
	 * @param range
	 */
	public void updateRange(Range range) {
		removeRange(range);
		addRange(range);
	}

	/**
	 * Call this when a new range has joined a group. This checks whether any
	 * groups are overlapping, and if, merges them.
	 */
	protected void joinGroups() {
		Collections.sort(overlapGroups, Range.byFrom);

		OverlapGroup next = overlapGroups.get(0);
		for (int i = 1; i < overlapGroups.size(); i++) {
			OverlapGroup current = next;
			next = overlapGroups.get(i);
			if (Range.Tools.overlapping(current, next)) {
				// move ranges to first group
				for (Range r : next) {
					rangeMapping.get(r).group = current;
				}
				next.join(current);
				next = current;
				// remove second group
				overlapGroups.remove(i--);
			}
		}
	}

	/**
	 * Call this when a range was removed from a group. This checks whether a
	 * group needs to be split.
	 */
	protected void splitGroups() {
		// TODO: actually, we only need to check one group.
		List<OverlapGroup> newGroups = new ArrayList<OverlapGroup>();
		for (OverlapGroup g : overlapGroups) {
			OverlapGroup newGroup = g.split();

			// is there at least one new group?
			if (newGroup != null && !newGroup.isEmpty()) {
				// try to split another group
				OverlapGroup otherNewGroup = newGroup.split();
				// now newGroup definitely is a group
				newGroups.add(newGroup);
				// is there anything left?
				while (otherNewGroup != null && !otherNewGroup.isEmpty()) {
					newGroup = otherNewGroup.split();
					newGroups.add(otherNewGroup);
					otherNewGroup = newGroup;
				}
			}
		}
		for (OverlapGroup g : newGroups) {
			for (Range r : g)
				rangeMapping.get(r).group = g;
		}

		overlapGroups.addAll(newGroups);
	}

	/**
	 * Updates the positions of all ranges
	 */
	public void updateGroupPositions() {
		for (OverlapGroup group : overlapGroups)
			updateGroupPositions(group);
	}

	/**
	 * Updates the positions of the ranges in one group.
	 * 
	 * @param group
	 */
	public void updateGroupPositions(OverlapGroup group) {
		// TODO: implement a better algorithm
		PriorityQueue<Range> byTo = new PriorityQueue<Range>(11, Range.byTo);
		byTo.addAll(group.getFromPriorityQueue());
		PriorityQueue<Range> byFrom = new PriorityQueue<Range>(group
				.getFromPriorityQueue());

		// get max collision count
		int maxcolls = 0;
		int colls = 0;
		while (!byFrom.isEmpty()) {
			if (byFrom.peek().getFrom() < byTo.peek().getTo()) {
				colls++;
				byFrom.remove();
			} else {
				colls--;
				byTo.remove();
			}
			if (colls > maxcolls)
				maxcolls = colls;
		}

		byTo = new PriorityQueue<Range>(11, Range.byTo);
		byTo.addAll(group.getFromPriorityQueue());
		byFrom = new PriorityQueue<Range>(group.getFromPriorityQueue());

		int spotheight = (int) (height / (double) maxcolls);
		PriorityQueue<Integer> spots = new PriorityQueue<Integer>();
		for (int i = 0; i < maxcolls; i++)
			spots.add(i * spotheight);

		while (!byFrom.isEmpty()) {
			if (byFrom.peek().getFrom() < byTo.peek().getTo()) {
				Range r = byFrom.remove();
				RangeInfo i = rangeMapping.get(r);
				i.height = spotheight;
				i.top = spots.remove();
				
				// check whether we can grab additional spots
				if (byFrom.size() == 0 || byFrom.peek().getFrom() >= r.getTo()) {
					List<Integer> additionalSpots = new ArrayList<Integer>();
					while(spots.size() > 0 && spots.peek() == i.top + spotheight*(additionalSpots.size()+1)) {
						additionalSpots.add(spots.remove());
					}
					i.height += additionalSpots.size() * spotheight;
					for(Integer spot : additionalSpots) {
						spots.add(spot);
					}
				}
			} else {
				Range r = byTo.remove();
				RangeInfo i = rangeMapping.get(r);
				spots.add(i.top);
			}
		}		
	}

	/**
	 * Removes a range from this overlap resolver and updates range positions.
	 * 
	 * @param range
	 */
	public void removeRange(Range range) {
		if (rangeMapping.containsKey(range)) {
			OverlapGroup group = rangeMapping.remove(range).group;
			group.removeRange(range);
			if (group.isEmpty())
				overlapGroups.remove(group);
			splitGroups();
			updateGroupPositions();
		}
	}

	public int getTop(Range range) {
		return rangeMapping.get(range).top;
	}

	public int getHeight(Range range) {
		return rangeMapping.get(range).height;
	}

	public Iterator<OverlapGroup> iterator() {
		return overlapGroups.iterator();
	}

}